//
//import java.util.LinkedList;
//import java.util.List;
//import java.util.Scanner;
//
//public class Main {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        List<Integer> list = new LinkedList<>();
//        int n = scanner.nextInt();
//        while(n-- > 0) {
//            int k = scanner.nextInt();
//            if(k == 0) {
//                int x = scanner.nextInt();
//                list.add(x);
//            }else if(k == 1) {
//                list.remove(list.size()-1);
//            }else {
//                int m = 0;
//                for(int i = 0; i<list.size();i++) {
//                    m = Math.max(m,list.get(i));
//                }
//                if(n == 1) {
//                    System.out.print(m);
//                }else {
//                    System.out.println(m);
//                }
//            }
//        }
//    }
//}

//
//import java.util.LinkedList;
//import java.util.List;
//import java.util.Scanner;
//
//public class Main {
//    public static void main(String[] args) {
//       Scanner scanner = new Scanner(System.in);
//       int V = scanner.nextInt();
//       int K = scanner.nextInt();
//       int[] v = new int[K+1]; //容量
//       int[] w = new int[K+1]; //价值
//       for(int i = 1; i<=K; i++)
//       {
//           v[i] = scanner.nextInt();
//           w[i] = scanner.nextInt();
//       }
//       int[][] dp = new int[K+1][V+1];
//
//       for(int i =1 ; i<=K; i++) {
//           for(int j =0; j<=V; j++) {
//               dp[i][j] = dp[i-1][j]; //不取
//               if(j >= v[i]) {
//                   dp[i][j] = Math.max(dp[i][j], dp[i-1][j-v[i]] + w[i]);
//               }
//           }
//       }
//
//        System.out.println(dp[K][V]);
//    }
//}

//
//
//import java.io.*;
//import java.util.HashMap;
//import java.util.LinkedList;
//import java.util.List;
//import java.util.Scanner;
//
//public class Main {
//    public static void main(String[] args) throws IOException {
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
//        String[] line = br.readLine().split(" ");
//        int N = Integer.parseInt(line[0]);
//        int K = Integer.parseInt(line[1]);
//        int[] nums = new int[N];
//        line = br.readLine().split(" ");
//
//        for(int i = 0 ;i<N; i++) {
//            nums[i] = Integer.parseInt(line[i]);
//        }
//
//        for(int i = 0; i<=N-K; i++) {
//            int min = Integer.MAX_VALUE;
//            for(int j = i; j<i+K; j++) {
//                min = Math.min(min,nums[j]);
//            }
//            pw.print(min + " ");
//        }
//        pw.println();
//        for(int i = 0; i<=N-K; i++) {
//            int max = Integer.MIN_VALUE;
//            for(int j = i; j<i+K; j++) {
//                max = Math.max(max,nums[j]);
//            }
//            pw.print(max + " ");
//        }
//        pw.flush();
//    }
//}

//
//import javax.security.auth.SubjectDomainCombiner;
//import java.util.Scanner;
//
//public class Main {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        int m = scanner.nextInt();
//        int[][] map = new int[n+1][m+1];
//        for(int i = 1; i<=n; i++) {
//            for(int j = 1; j<=m; j++) {
//                map[i][j] = scanner.nextInt();
//            }
//        }
//    }
//}

//
//import java.io.BufferedReader;
//import java.io.InputStreamReader;
//import java.io.OutputStreamWriter;
//import java.io.PrintWriter;
//import java.util.LinkedList;
//import java.util.List;
//import java.util.Scanner;
//import java.util.Stack;
//
//public class Main {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
//        List<Integer> list = new LinkedList<>();
//        Stack<Integer> stack = new Stack<>();
//        int n = scanner.nextInt();
//        while(n-- > 0) {
//            int k = scanner.nextInt();
//            if(k == 0) {
//                int x = scanner.nextInt();
//                list.add(x);
//                if(stack.isEmpty() || x >= stack.peek()) {
//                    stack.add(x);
//                }
//            }else if(k == 1) {
//                if(list.size()>0) {
//                    int peek = list.get(list.size()-1);
//                    list.remove(list.size()-1);
//                    if(!stack.isEmpty()&&stack.peek() == peek) {
//                        stack.pop();
//                    }
//                }
//            }else {
//                int m = 0;
//                if(stack.isEmpty()) System.out.println(0);
//                else System.out.println(stack.peek());
//            }
//        }
//    }
//}

//1 3 2 4 9 5
//1 3   4 9

//
//import java.io.*;
//import java.util.LinkedList;
//import java.util.List;
//import java.util.Scanner;
//import java.util.Stack;
//
//public class Main {
//    public static void main(String[] args) throws IOException {
//        Scanner scanner = new Scanner(System.in);
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
//        List<Integer> list = new LinkedList<>();
//        Stack<Integer> stack = new Stack<>();
//        int n = scanner.nextInt();
//        while(n-- > 0) {
//            String[] line = br.readLine().split(" ");
//            int k = Integer.parseInt(line[0]);
//            if(k == 0) {
//                int x = Integer.parseInt(line[1]);
//                list.add(x);
//                if(stack.isEmpty() || x >= stack.peek()) {
//                    stack.add(x);
//                }
//            }else if(k == 1) {
//                if(list.size()>0) {
//                    int peek = list.get(list.size()-1);
//                    list.remove(list.size()-1);
//                    if(!stack.isEmpty()&&stack.peek() == peek) {
//                        stack.pop();
//                    }
//                }
//            }else {
//                int m = 0;
//                if(stack.isEmpty()) pw.println(0);
//                else pw.println(stack.peek());
//            }
//        }
//        pw.flush();
//    }
//}


